We present a novel analysis of the expected risk of weighted majority vote in multiclass classification. The analysis takes correlation of predictions by ensemble members into account and provides a bound that is amenable to efficient minimization, which yields improved weighting for the majority vote. We also provide a specialized version of our bound for binary classification, which allows to exploit additional unlabeled data for tighter risk estimation. In experiments, we apply the bound to improve weighting of trees in random forests and show that, in contrast to the commonly used first order bound, minimization of the new bound typically does not lead to degradation of the test error of the ensemble.

We investigate a stochastic counterpart of majority votes over finite ensembles of classifiers, and study its generalization properties. While our approach holds for arbitrary distributions, we instantiate it with Dirichlet distributions: this allows for a closed-form and differentiable expression for the expected risk, which then turns the generalization bound into a tractable training objective.The resulting stochastic majority vote learning algorithm achieves state-of-the-art accuracy and benefits from (non-vacuous) tight generalization bounds, in a series of numerical experiments when compared to competing algorithms which also minimize PAC-Bayes objectives -- both with uninformed (data-independent) and informed (data-dependent) priors.

Federated learning (FL) faces challenges in ensuring both privacy and communication efficiency, particularly in resource-constrained environments such as Internet of Things (IoT) and edge networks. While sign-based methods, such as sign stochastic gradient descent with majority voting (SIGNSGD-MV), offer substantial bandwidth savings, they remain vulnerable to inference attacks due to exposure of gradient signs. Existing secure aggregation techniques are either incompatible with sign-based methods or incur prohibitive overhead. To address these limitations, we propose Hi-SAFE, a lightweight and cryptographically secure aggregation framework for sign-based FL. Our core contribution is the construction of efficient majority vote polynomials for SIGNSGD-MV, derived from Fermat's Little Theorem. This formulation represents the majority vote as a low-degree polynomial over a finite field, enabling secure evaluation that hides intermediate values and reveals only the final result. We further introduce a hierarchical subgrouping strategy that ensures constant multiplicative depth and bounded per-user complexity, independent of the number of users n.

Neural Information Processing Systems http://nips.cc/

We collected the annotations with four human workers. Three of them were hired workers which replied to a local job advertisement and were paid 11 C per hour. The last worker was a domain expert who desired no further payment than their contribution to science.

Thus, we expect our findings to hold here as well.

The bound is based on a novel parametric form of the Chebyshev-Cantelli inequality (a.k.a.

Here we introduce a few more notations. In this section we provide the details of the subroutines used in the training algorithm for Frugal ML . There are 3 steps for solving problem 3.3. T o solve Problem 3.2, let us first denote C.1 Helpful Lemmas W e first provide some useful lemmas throughout this section. Lemma 4. Suppose the linear optimization problem max Lemma 5. Let F (w) be the optimal value of the linear optimization problem max Thus, the objective value must be smaller than the optimal one, i.e., Given the expected accuracy and cost provided by Lemma 2, the problem 3.1 becomes Let us first consider the expected accuracy .

Weighted majority vote is a fundamental technique for combining predictions of multiple classifiers.